//
// Created by ASUS on 2024/3/6.
//

#include <bits/stdc++.h>

using namespace std;

void halfInsertSort(vector<int>&nums){
	int n=nums.size();
	int i,j,low,high,mid,temp;
	for(i=1;i<=n;i++){
		for(int k=0;k<n;k++){
			cout<<nums[k]<<" ";
		}
		cout<<endl;
		temp=nums[i];
		low=0;
		high=i-1;
		while (low<=high){
			mid=(low+high)/2;
			if(nums[mid]>temp)
				high=mid-1;
			else
				low=mid+1;
		}
		for(j=i-1;j>=high+1;--j)
			nums[j+1]=nums[j];
		nums[high+1]=temp;
	}
}